package com.heima.leetcode.datastructure.heap;

import java.util.PriorityQueue;

/**
 * <strong>用自己系统的PriorityQueue查找数据流的中位数 295</strong>
 * <ul>
 *     <li>如果直接遍历排序效率低</li>
 *     <li>可以把数据流分为两个相当大小的部分，前半和后半</li>
 *     <li>前半用大顶堆来存储，只关心前半部分的最大值</li>
 *     <li>后半用小顶堆来存储，只关心后半部分的最小值</li>
 *     <li>怎么保证大顶堆内元素的个数等于小顶堆内元素的个数呢
 *         <ol>
 *             <li>可以规定当两个堆中的元素个数相等时，往大顶堆中加入一个元素</li>
 *             <li>可以规定当两个堆中的元素个数不等时，往小顶堆中加入一个元素</li>
 *         </ol>
 *     </li>
 *     <li>如何保证大顶堆里面存的就是前半部分，小顶堆里面存的就是后半部分呢
 *         <ol>
 *             <li>当将要往大顶堆中放入元素时，不要直接放入，而是先放入小顶堆中，再让小顶堆重构后吐出一个堆顶元素加到小顶堆中</li>
 *             <li>当将要往小顶堆中放入元素时，不要直接放入，而是先放入大顶堆中，再让大顶堆重构后吐出一个堆顶元素加到大顶堆中</li>
 *         </ol>
 *     </li>
 *     <li>因为数据流是会变化的，会增大，所以当堆为满的时候应该实现自动扩容</li>
 * </ul>
 * @author 勾新杰
 * @version 1.0
 * @date 2024/9/7 11:58
 */
public class MedianFinder2 {
    private final PriorityQueue<Integer> leftHeap;
    private final PriorityQueue<Integer> rightHeap;

    {
        // 第一点：很重要很重要：源码其实就是一个广义的小顶堆，无论怎么传比较器，最"小"的永远在堆顶
        // 第二点：如果构造器没有传比较器，就会传替换泛型的类的Comparable接口的比较方法，进行比较，建立小顶堆。
        // 实现这个比较器接口，参数为(o1,o2)，o1>o2返回1，o1=o2返回0，o1<o2返回-1.
        // 源码中会调用比较器接口的compare方法，进行子节点和父节点的比较，如果子节点"大"于父节点，才交换，也就是if(comparator.compare(子节点，父节点) < 0){swap(子节点，父节点)}
        // 所以如果要实现大顶堆，要把比较器"颠倒"一下
        leftHeap = new PriorityQueue<>((o1,o2)-> Integer.compare(o2,o1));

        rightHeap = new PriorityQueue<>();
    }

    public MedianFinder2() {
    }

    public MedianFinder2(int[] arr){
        for (Integer i : arr) {
            addNum(i);
        }
    }

    public void addNum(int num){
        if (leftHeap.size() == rightHeap.size()){
            rightHeap.offer(num);
            leftHeap.offer(rightHeap.poll());
        }else{
            leftHeap.offer(num);
            rightHeap.offer(leftHeap.poll());
        }
    }

    public double findMedian(){
        if (leftHeap.isEmpty() && rightHeap.isEmpty()){
            throw new IllegalArgumentException("数据流中没有元素");
        }
        if (leftHeap.size() > rightHeap.size()){
            return leftHeap.peek();
        } else if (rightHeap.size() > leftHeap.size()) {
            return rightHeap.peek();
        }
        return (leftHeap.peek() + rightHeap.peek()) / 2.0;
    }

    @Override
    public String toString() {
        return "左半部分：" +
                leftHeap.toString() +
                " "+
                rightHeap.toString() +
                "：右半部分" ;
    }
}
